package cn.yuemouren.leetcode;

/**
 * @Author: Timi
 * @Description: 5. 最长回文子串  中心规划算
 * @Date: 2020/8/18 10:23
 */
public class Test_5 {

    private int index,length;

    public String longestPalindrome(String s) {

        if(s.length() < 2)
            return s;

        for (int i = 0; i < s.length(); i++){
            palindromeHelper(s,i,i);
            palindromeHelper(s,i,i+1);
        }
        return s.substring(index,index+length);
    }

    public void palindromeHelper(String s,int l,int r){

        while(l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)){
            l--;
            r++;
        }
        if(length < r - l -1){
            index = l + 1;
            length = r - l - 1;
        }
    }

    public static void main(String[] args) {
        String str = "babad";
        new Test_5().longestPalindrome(str);
    }
}

/**
 * public String longestPalindrome(String s) {
 *
 *         if(s.length() < 2)
 *             return s;
 *
 *         int start = 0,end = 0;
 *
 *         for (int i = 0; i < s.length(); i++){
 *             int j = palindromeHelper(s, i, i);
 *             int o = palindromeHelper(s,i,i+1);
 *             int max = Math.max(j, o);
 *             if(max > end - start){
 *                 start = i - (max - 1) / 2;
 *                 end = i + max / 2;
 *             }
 *         }
 *         return s.substring(start,end + 1);
 *     }
 *
 *     public int palindromeHelper(String s,int left,int right){
 *
 *         int l = left,r = right;
 *         while(l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)){
 *             l--;
 *             r++;
 *         }
 *         return r - l - 1;
 *     }
 */
